import {TreeNode} from "./Tree.mjs";

/**
 * https://leetcode.cn/problems/binary-tree-level-order-traversal/description/?envType=study-plan-v2&envId=top-100-liked
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[9,20],[15,7]]
 * 遍历写法
 * @param root
 */
function levelOrder1(root: TreeNode | null): number[][] {
    if (root === null) return []
    let res: number[][] = []
    let temp: number[] = []
    let queue: TreeNode[] = [root as TreeNode]
    while (queue.length > 0) {
        const levelSize = queue.length // 当前节点的数量
        for (let i = 0; i < levelSize; i++) {
            const node = queue.shift()!
            temp.push(node.val)
            node?.left && queue.push(node.left)
            node?.right && queue.push(node.right)
        }

        res.push(temp)
        temp = []
    }
    return res
};

/**
 * 递归写法
 * @param root
 */
function levelOrder(root: TreeNode | null): number[][] {
    if (root === null) return []
    let res: number[][] = []
    const digui = (root: TreeNode | null, level: number) => {
        if (root === null) return
        if (res.length === level) {
            res.push([])
        }
        res[level].push(root.val)
        digui(root.left, level + 1)
        digui(root.right, level + 1)
    }
    digui(root, 0)
    return res
};

console.log(JSON.stringify(levelOrder(new TreeNode(1, new TreeNode(2, new TreeNode(4)), new TreeNode(3, new TreeNode(5))))));